package com.lili.greedy;

import java.util.*;

/**
 * @Auther: 李 力
 * @Date: 2024/8/6
 * @Description: 0-1背包问题
 * @version: 1.0
 */
public class BaiBao01 {
    /*
        1. n个物品都是固体，有重量和价值
        2. 现在你要取走不超过10克的物品
        3. 与分数背包问题的区别：每次可以不拿或全拿，问最高价值是多少

           编号 重量(g)  价值(元)                         简称
            1    4       1600           黄金一块   400      A
            2    8       2400           红宝石一粒 300      R
            3    5       30             白银一块            S
            0    1       1000000        钻石一粒            D
     */
    //total：不超过的数目
    public static Map<String, Integer> select(Item[] items, int total) {
        Arrays.sort(items, Comparator.comparingInt(Item::getUnitValue).reversed());
        //最大价值
        int maxNum = 0;
        HashMap<String, Integer> map = new HashMap<>();
        for (Item item : items) {
            if (total >= item.getWeight()) {
                total = total - item.getWeight();
                maxNum = maxNum + item.getValue();
                map.put(item.getName(), item.getWeight());
            }
        }
        map.put("最大价值", maxNum);
        return map;
    }

    public static void main(String[] args) {
        Item[] items = new Item[]{
                new Item(1, 4, 1600, "黄金"),
                new Item(2, 8, 2400, "宝石"),
                new Item(3, 5, 30, "白银"),
                new Item(4, 1, 10_000, "钻石"),
        };
        Map<String, Integer> map = select(items, 10);
        map.forEach((key, value) -> {
            System.out.println(key + ":" + value);
        });
    }
    /*
     * 结论
     *最大价值:11630
      白银:5
      钻石:1
      黄金:4
     *明显不是最有解，01的背包问题在后续的动态规划中得出最优解
     *
     * */
}
